﻿//仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。
//请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。
//
//输入：stock = [2, 5, 7, 4], cnt = 1
//输出：[2]
//
//输入：stock = [0, 2, 3, 6], cnt = 2
//输出：[0, 2] 或[2, 0]
//
//提示：
//	0 <= cnt <= stock.length <= 10000
//	0 <= stock[i] <= 10000

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& nums, int k) {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1, k);
        return { nums.begin(), nums.begin() + k };
    }
    void qsort(vector<int>& nums, int l, int r, int k) {
        if (l >= r)
            return;
        // 1.随机选择⼀个基准元素+数组分三块

        int key = getRandom(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (nums[i] < key)
                swap(nums[++left], nums[i++]);
            else if (nums[i] == key)
                i++;
            else
                swap(nums[--right], nums[i]);
        }
        // [l, left][left + 1, right - 1] [right, r]
        // 2.分情况讨论

        int a = left - l + 1, b = right - left - 1;
        if (a > k)
            qsort(nums, l, left, k);
        else if (a + b >= k)
            return;
        else
            qsort(nums, right, r, k - a - b);
    }
    int getRandom(vector<int>& nums, int l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
};